题目 解密QQ号 鱼的记忆 程序输入问题 查找 x 第一个大于等于 x 的数 第一个大于 x 的数 【二分查找】最后一个小于等于 x
解密QQ号
题目大意
小码酱给了一串加密的数字字符串（最多 101010 位），它是她的 QQ 号的加密形式。
解密规则如下：
1. 将第 111 个数从串头取出，记入解密后的 QQ 号；
2. 将第 222 个数移动到串尾；
3. 删除第 333 个数，记入 QQ 号；
4. 移动第 444 个数到串尾；
5. ...
依此类推，交替执行“删除加入结果”与“移动到尾部”操作，直到队列中只剩一个数字，将它也删掉并加入结果。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
这个过程非常符合**队列结构（FIFO）**的行为：
* 每次处理当前队首元素；
* 若处于“删除并加入结果”轮次，则记录下来；
* 若处于“移到尾部”轮次，则将该元素重新加入队尾；
* 直到队列为空，整个解密结束。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
1. 将字符串中每个字符依次入队；
2. 使用一个标志变量（如 turn = true/false）控制当前操作是“删除加入结果”还是“移动到队尾”；
3. 持续处理队首元素，直到队列清空。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 每个字符最多被操作两次（一次加入结果，一次移动到尾）；
* 所以总时间复杂度为 O(n)\boxed{O(n)}O(n) ，其中 nnn 为字符串长度，最多为 101010；
* 空间复杂度也是 O(n)O(n)O(n)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
鱼的记忆
题目大意
小码君正在学习字符，但他的记忆力有限，他最多能同时记住 mmm 个字符。
给定一个长度为 nnn 的字符序列，当他遇到不认识的字符时会查看书本：
* 若当前记忆未满，则将该字符加入记忆；
* 若当前已记满 mmm 个字符，则先忘掉最早记住的那个，再记住新字符；
* 若字符已在记忆中，则不需要查看书本。
求整个过程中，小码君总共查看书本的次数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
本题等价于一个固定长度的先进先出缓存队列（FIFO），当缓存中没有某元素时，需要“缓存替换”。
我们要模拟这个缓存系统，判断每个字符是否已经存在于缓存中，若没有则计数并按规则更新队列。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
1. 使用一个队列 q 模拟小码君的记忆，最大长度为 mmm；
2. 遍历输入的 nnn 个字符：
* 如果字符已存在于 q 中，跳过；
* 否则：
* 查看书本，计数器加一；
* 如果队列未满，直接加入；
* 如果已满，弹出队首（最早记住的字符），再加入新字符；
3. 最终输出查看书本的总次数。
优化技巧
* 为避免每次都线性扫描队列判断字符是否存在，可以使用 unordered_set<char> 或 set<char> 进行快速查找；
* 当前代码用纯 queue 实现，也可通过两次循环保证正确性（当前数据范围 n≤100n \le 100n≤100 足够使用此法）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
原始实现：
* 每次判断字符是否已在队列中，复杂度 O(m)O(m)O(m)；
* 总共 nnn 个字符，整体复杂度 O(n⋅m)O(n \cdot m)O(n⋅m)；
由于 n≤100n \le 100n≤100，m≤10m \le 10m≤10，所以最大操作量为 100010001000，可以接受。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
程序输入问题
题目大意
程序员在敲代码时可能会出现错误，采用如下两种方式进行补救：
* 退格符 #：表示撤销上一个字符；
* 退行符 @：表示整行清空，即撤销从上一个换行符到当前位置之间的所有输入。
你将获得若干行输入数据，每一行都表示一次输入，直到遇到 ****** 为止。
请你模拟每一行的输入处理过程，输出最终每一行的“有效字符串”。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
该问题需要模拟用户的输入行为，本质上是：
* 对字符流进行逐个解析；
* 支持 “撤销最后一个字符” 的栈操作；
* 支持 “清空整行” 的栈清空操作。
因此，非常适合使用 栈（stack） 来实现：
* 入栈表示输入字符；
* # 表示弹出栈顶；
* @ 表示清空整个栈；
* 最终将栈内字符拼接还原为字符串即为所求。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
1. 读取每一行字符串，直到遇到结束标志 "******"；
2. 对于每一行，使用一个栈模拟编辑过程：
* 普通字符：压入栈；
* #：如果栈不为空，则弹出一个字符；
* @：清空整个栈；
3. 最后将栈中字符倒序拼接为最终结果字符串；
4. 每一行输出一行结果。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 每行最多处理 100100100 个字符；
* 每个字符处理操作为 O(1)O(1)O(1)；
* 假设总共有 LLL 行，总复杂度为 O(L⋅n)O(L \cdot n)O(L⋅n)，其中 nnn 是每行长度，最大为 100100100；
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
查找 X
题目大意
给定一个升序排列的长度为 nnn 的整数序列，所有元素互不相同。
请你查找某个整数 xxx 是否存在于该序列中：
* 如果存在，输出 xxx 在序列中的位置（下标从 111 开始）；
* 如果不存在，输出 −1-1−1。
题目要求使用 二分查找 完成。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
由于序列是升序且无重复元素，非常适合使用二分查找进行快速定位。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
使用经典的二分查找模板：
1. 设置左右指针 l=1,r=nl = 1, r = nl=1,r=n（注意从 111 开始）；
2. 每次取中点 mid=⌊l+r2⌋mid = \lfloor \frac{l + r}{2} \rfloormid=⌊2l+r ⌋；
3. 判断：
* 若 a[mid]=xa[mid] = xa[mid]=x，则找到了，输出 midmidmid；
* 若 a[mid]>xa[mid] > xa[mid]>x，说明目标在左侧，令 r=mid−1r = mid - 1r=mid−1；
* 若 a[mid]<xa[mid] < xa[mid]<x，说明目标在右侧，令 l=mid+1l = mid + 1l=mid+1；
4. 循环结束后若未找到，则输出 −1-1−1。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 每次查找将搜索区间缩小一半；
* 最多执行 log2n\log_2 nlog2 n 次比较；
* 所以时间复杂度为 O(logn)\boxed{O(\log n)}O(logn) ；
* 对于 n≤100n \le 100n≤100，效率非常高。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
第一个大于等于 X 的数
题目大意
给定一个长度为 nnn 的升序序列（可能包含重复元素），请你查找第一个大于等于某个数 xxx 的元素的下标（从 111 开始）。
如果这样的元素存在，输出其下标；如果不存在（即 xxx 比所有元素都大），也要输出 −1-1−1。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
这是一个经典的二分查找变形问题，即找第一个满足条件的下标（也叫左侧边界查找）。
给定序列是升序的，允许重复元素，目标是：
> 找到第一个 a[i]≥xa[i] \ge xa[i]≥x 的下标 iii。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
采用二分查找模板进行变形：
1. 初始化左右边界：l=1,r=nl = 1, r = nl=1,r=n；
2. 每次取中点 mid=⌊l+r2⌋mid = \lfloor \frac{l + r}{2} \rfloormid=⌊2l+r ⌋；
3. 判断：
* 若 a[mid]≥xa[mid] \ge xa[mid]≥x，记录当前位置为候选解，并继续向左查找（r=mid−1r = mid - 1r=mid−1）；
* 否则，说明当前位置过小，向右查找（l=mid+1l = mid + 1l=mid+1）；
4. 循环结束后，输出记录的下标（若没找到则为 −1-1−1）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 每轮搜索将范围减半，最多进行 log2n\log_2 nlog2 n 次；
* 所以时间复杂度为 O(logn)\boxed{O(\log n)}O(logn) ；
* 空间复杂度为 O(1)O(1)O(1)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
第一个大于 X 的数
题目大意
给定一个升序数组（可能有重复元素），你需要找到其中第一个严格大于某个整数 xxx 的元素下标（下标从 111 开始）。
* 若存在这样的元素，输出其下标；
* 若不存在（即 xxx 不小于所有元素），输出 −1-1−1。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
本题本质是一个标准的二分查找左侧边界问题（upper bound 查找）。
目标是找到最小的 iii，使得 a[i]>xa[i] > xa[i]>x 成立。
注意与上一题（查找第一个 ≥x\ge x≥x）的区别：此题要求严格大于。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
采用标准二分查找模板进行修改：
1. 初始化左右边界 l=1,r=nl = 1, r = nl=1,r=n；
2. 使用变量 ans 记录满足条件的位置，初始为 −1-1−1；
3. 在循环中不断取中点：
* 若 a[mid]>xa[\text{mid}] > xa[mid]>x，说明当前元素可能是答案，同时可能左边还有更小的符合条件的值，故令 r=mid−1r = \text{mid} - 1r=mid−1，并记录 ans = mid；
* 否则说明 a[mid]≤xa[\text{mid}] \le xa[mid]≤x，不符合要求，向右搜索，令 l=mid+1l = \text{mid} + 1l=mid+1；
4. 循环结束后输出 ans 即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 每轮查找将区间折半，最多执行 log2n\log_2 nlog2 n 次；
* 所以时间复杂度为 O(logn)\boxed{O(\log n)}O(logn) ；
* 空间复杂度为 O(1)O(1)O(1)，不使用额外数组。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
【二分查找】LOWER_BOUND 函数
题目大意
给定一个升序排列（元素可能重复）的长度为 nnn 的整数序列，要求使用 lower_bound 函数，查找第一个 大于等于 xxx 的元素，并输出其下标（从 111 开始）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
这是标准的二分查找变形题，要求使用 STL 中的 lower_bound 函数。
什么是 LOWER_BOUND？
* 在一个有序区间中，lower_bound(first, last, x) 返回第一个不小于 xxx 的位置；
* 它等价于：在区间中找最小的下标 iii 满足 a[i]≥xa[i] \ge xa[i]≥x；
* 若不存在满足条件的元素，返回 last。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
1. 输入数据时从下标 111 开始存储；
2. 使用 lower_bound(a + 1, a + n + 1, x) 来查找；
3. 最后返回的是一个指针，减去 a 即可得到下标；
4. 若 xxx 比所有元素都大，返回的下标会是 n+1n + 1n+1，即越界，也符合题意（即没找到）；
* 如需判断是否找到，可加判断 if (pos <= n)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* lower_bound 内部是用二分查找实现的；
* 时间复杂度为 O(logn)\boxed{O(\log n)}O(logn) ；
* 空间复杂度为 O(1)O(1)O(1)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
【二分查找】UPPER_BOUND 函数
题目大意
给定一个长度为 nnn 的升序序列（元素可能重复），查找第一个 严格大于 xxx 的元素的位置，并输出其下标（从 111 开始）。
本题要求使用 STL 的 upper_bound 函数来实现。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
这是一个经典的 二分查找右边界 问题，即：
> 在升序序列中找第一个满足 a[i]>xa[i] > xa[i]>x 的位置。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
函数说明
UPPER_BOUND(BEGIN, END, X)
* 作用：返回第一个严格大于 xxx 的位置；
* 实现方式：标准二分查找；
* 时间复杂度：O(logn)\boxed{O(\log n)}O(logn) ；
* 返回的是一个指针/迭代器，需要通过减去基地址转换为下标。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
1. 将输入数组从下标 111 开始读入；
2. 使用 upper_bound(a + 1, a + n + 1, x) 查找；
3. 该函数返回的是指针，减去 a 得到下标；
4. 若 xxx 大于等于所有元素，则返回 n+1n + 1n+1，表示“未找到”。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
【二分查找】最后一个小于等于 X
题目大意
给定一个升序数组（元素可能重复），要求找到最后一个小于等于给定整数 xxx 的元素下标（从 111 开始）。如果找不到，输出 −1-1−1。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
这是一个二分查找右边界问题，即：
> 在升序序列中查找最大的 iii，使得 a[i]≤xa[i] \le xa[i]≤x。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
我们可以使用以下三种方法实现该查找：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
方法一：STL UPPER_BOUND
原理解释：
* upper_bound(first, last, x) 返回第一个满足 a[i]>xa[i] > xa[i]>x 的迭代器；
* 所以最后一个 ≤x\le x≤x 的元素一定在它的前一个位置；
* 故：pos = upper_bound(...) - a - 1。
注意：
* 若 upper_bound 返回的是 a + 1，说明没有任何元素 ≤x\le x≤x，应特判输出 -1。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
方法二：用 LOWER_BOUND(X + 1) 等价替代
原理解释：
* lower_bound(first, last, x + 1) 返回第一个 ≥x+1\ge x + 1≥x+1 的位置；
* 也就是第一个 >x> x>x 的位置；
* 同理，前一个就是最后一个 ≤x\le x≤x 的位置。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
方法三：手写二分查找（推荐掌握）
原理解释：
* 满足 a[mid]≤xa[\text{mid}] \le xa[mid]≤x 时，继续往右找；
* 记录满足条件的最大下标 ans；
* 若找不到，ans 仍为 -1。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
三种方法均使用二分查找，其时间复杂度为：
O(logn)\boxed{O(\log n)}O(logn)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
完整代码（包含三种方法）
